|
In computer science, a loop is a programming language statement that allows code to be repeatedly executed; an invariant of a loop is a property that holds before (and after) each repetition. It is a logical assertion, sometimes programmed as an assertion. Knowing its invariant(s) is essential for understanding the effect of a loop. In formal program verification, in particular in the Floyd-Hoare approach, loop invariants are expressed in formal predicate logic and used to prove properties of loops and, by extension, algorithms employing loops (usually correctness properties). A loop invariant should be true on entry into a loop and is guaranteed to remain true after every iteration of the loop. This means that on exit from the loop both the loop invariant and the loop termination condition can be guaranteed. Because of the fundamental similarity of loops and recursive programs, proving partial correctness of loops with invariants is very similar to proving correctness of recursive programs via induction. In fact, the loop invariant is often the inductive property- the induction hypothesis- one has to prove of a recursive program that is equivalent to a given loop. ==Informal example== The following C subroutine max() returns the maximum value of its argument array a) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「loop invariant」の詳細全文を読む スポンサード リンク
|